package cn.qyd.leecode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 家族继承顺序问题
 *
 * @author 邱运铎
 * @date 2024-04-08 19:45
 */
public class InherentOrder {
    public static void main(String[] args) {
        ThroneInheritance king = new ThroneInheritance("king");
        king.birth("king", "andy");
        king.birth("king", "Bob");
        king.birth("king", "catherine");
        king.birth("andy", "matthew");
        king.birth("Bob", "alex");
        king.birth("Bob", "asha");
        System.out.println(king.sonMap);
        System.out.println(king.isDeaths);
        System.out.println(king.getInheritanceOrder());
        king.death("Bob");
        System.out.println(king.getInheritanceOrder());
    }

    static class ThroneInheritance {
        private Map<String, List<String>> sonMap;
        private Map<String,Boolean> isDeaths;
        private String kingName;

        public ThroneInheritance(String kingName) {
            sonMap = new HashMap<>();
            isDeaths = new HashMap<>();
            this.kingName = kingName;
            sonMap.put(kingName, new ArrayList<>());
            isDeaths.put(kingName, false);

        }

        public void birth(String parentName, String childName) {
            if (sonMap.containsKey(parentName)) {
                sonMap.get(parentName).add(childName);
            } else {
                ArrayList<String> curSonList = new ArrayList<>();
                curSonList.add(childName);
                sonMap.put(parentName, curSonList);
            }

            isDeaths.put(childName, false);
        }

        public void death(String name) {
            isDeaths.put(name, true);
        }

        public List<String> getInheritanceOrder() {
            List<String> curInheritanceOrder = new ArrayList<>();
            if (!isDeaths.get(kingName)) {
                curInheritanceOrder.add(kingName);
            }
            dfs(curInheritanceOrder, kingName);
            return curInheritanceOrder;
        }

        public void dfs(List<String> curInheritanceOrder, String name) {
            if (sonMap.containsKey(name)) {
                List<String> curSons = sonMap.get(name);

                for (int i = 0; i < curSons.size(); i++) {
                    if (!isDeaths.get(curSons.get(i))) {
                        curInheritanceOrder.add(curSons.get(i));
                    }
                    dfs(curInheritanceOrder, curSons.get(i));
                }
            }
        }
    }
}
